A river crossing puzzle is a type of puzzle in which the object is to carry items from one
river bank to another, usually in the fewest trips. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or which or how many items may be safely left together.
[.] The setting may vary cosmetically, for example, by replacing the river by a bridge.
The earliest known river-crossing problems occur in the manuscript ''
Propositiones ad Acuendos Juvenes The medieval Latin manuscript ''Propositiones ad Acuendos Juvenes'' ( en, Problems to Sharpen the Young) is one of the earliest known collections of recreational mathematics problems.Alcuin
Alcuin of York (; la, Flaccus Albinus Alcuinus; 735 – 19 May 804) – also called Ealhwine, Alhwin, or Alchoin – was a scholar, clergyman, poet, and teacher from York, Northumbria. He was born around 735 and became the student o ...
. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the
fox, goose and bag of beans puzzle
The wolf, goat and cabbage problem is a river crossing puzzle. It dates back to at least the 9th century, and has entered the folklore of several cultures.
The story
A farmer with a wolf, a goat, and a cabbage must cross a river by boat. The bo ...
and the
jealous husbands problem
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems, river-crossing logic puzzles. The missionaries and cannibals problem is a well-known toy problem in artificial intellige ...
.
Well-known river-crossing puzzles include:
* The
fox, goose and bag of beans puzzle
The wolf, goat and cabbage problem is a river crossing puzzle. It dates back to at least the 9th century, and has entered the folklore of several cultures.
The story
A farmer with a wolf, a goat, and a cabbage must cross a river by boat. The bo ...
, in which a farmer must transport a fox, goose and bag of beans from one side of a river to another using a boat which can only hold one item in addition to the farmer, subject to the constraints that the fox cannot be left alone with the goose, and the goose cannot be left alone with the beans. Equivalent puzzles have also been stated involving a fox, chicken, and bag of grain, or a
wolf, goat, and cabbage, etc.
* The
jealous husbands problem
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems, river-crossing logic puzzles. The missionaries and cannibals problem is a well-known toy problem in artificial intellige ...
, in which three married couples must cross a river using a boat which can hold at most two people, subject to the constraint that no woman can be in the presence of another man unless her husband is also present. This is similar to the
missionaries and cannibals problem
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing logic puzzles. The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used b ...
, in which three missionaries and three cannibals must cross the river, with the constraint that at any time when both missionaries and cannibals are standing on either bank, the cannibals on that bank may not outnumber the missionaries.
* The
bridge and torch problem.
* ''Propositio de viro et muliere ponderantibus plaustrum''. In this problem, also occurring in ''Propositiones ad Acuendos Juvenes'', a man and a woman of equal weight, together with two children, each of half their weight, wish to cross a river using a boat which can only carry the weight of one adult.
These problems may be analyzed using
graph-theoretic
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
methods, by
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
,
[.] or by
integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
.
[.]
See also
*
Vertex cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimiza ...
References
External links
YouTube video
{{DEFAULTSORT:River Crossing Puzzle
Logic puzzles